import java.util.*;

public class Solution {

    public int maxVowels(String s, int k) {
        char[] tmp = new char[]{'a','e','o','i','u'};
        Set<Character> hash = new HashSet<>();
        for(char x : tmp){
            hash.add(x);
        }

        int ret = 0, count = 0;
        char[] ch = s.toCharArray();
        for(int i = 0; i < ch.length; i++){
            if(hash.contains(ch[i])){
                count++;
            }
            if(i < k - 1){ continue;}
            ret = Math.max(ret, count);
            if(hash.contains(ch[i - k + 1])){
                count--;
            }
        }
        return ret;
    }

    public double findMaxAverage(int[] nums, int k) {
        int sum = 0, ret = Integer.MIN_VALUE;

        for(int i = 0; i < nums.length; i++){
            sum += nums[i];
            if(i < k - 1) { continue;}
            ret = Math.max(ret, sum);
            sum -= nums[i - k + 1];
        }
        return (double) ret / k;
    }

    public int numOfSubarrays(int[] arr, int k, int threshold) {
        int ret = 0, sum = 0;

        for(int i = 0; i < arr.length; i++){
            sum += arr[i];
            if(i < k - 1) { continue;}
            if(sum >= threshold * k){
                ret++;
            }
            sum -= arr[i - k + 1];
        }
        return ret;
    }

    public int[] getAverages(int[] nums, int k) {
        int[] ret = new int[nums.length];
        Arrays.fill(ret, -1);
        long sum = 0;
        for(int i = 0; i < nums.length; i++){
            sum += nums[i];
            if(i < k * 2) { continue;}
            ret[i - k] = (int) (sum / (k * 2 + 1));
            sum -= nums[i - k * 2];
        }
        return ret;
    }

    public static int minimumRecolors1(String blocks, int k) {
        int n = blocks.length();
        char[] ch = blocks.toCharArray();
        int ret = 0, count = 0;
        for(int left = 0, right = 0; right < n;){
            while(right < k){
                if(ch[right] == 'w') { count++;}
                right++;
                ret = count;
            }
            count -= ch[left] == 'w' ? 1 : 0;
            count += ch[right] == 'w' ? 1 : 0;
            ret = Math.min(ret, count);
            left++;
            right++;
        }
        return ret;
    }

    public static int minimumRecolors(String blocks, int k) {
        int left = 0, right = 0, count = 0;
        while(right < k){
            count += blocks.charAt(right) == 'w' ? 1 : 0;
            right++;
        }
        int ret = count;
        while(right < blocks.length()){
            count -= blocks.charAt(left) == 'w' ? 1 : 0;
            count += blocks.charAt(right) == 'w' ? 1 : 0;
            ret = Math.min(ret, count);
            left++;
            right++;
        }
        return ret;
    }

    public static long maxSum1(List<Integer> nums, int m, int k) {
        Map<Integer, Integer> hash = new HashMap<>();
        int ret = 0, sum = 0, kind = 0;

        for(int i = 0; i < nums.size(); i++){
            sum += nums.get(i);
            hash.put(nums.get(i), hash.getOrDefault(nums.get(i), 0) + 1);
            if(hash.get(nums.get(i)) == 1) { kind++;}

            if(i < k - 1) { continue;}

            if(kind > k) { ret = Math.max(ret, sum);}
            sum -= nums.get(i - k + 1);
            hash.put(nums.get(i - k + 1), hash.get(nums.get(i - k + 1)) - 1);
            if(hash.get(nums.get(i - k + 1)) == 0) { kind--;}
        }
        return ret;
    }

    public long maxSum(List<Integer> nums, int m, int k) {
        Map<Integer, Integer> hash = new HashMap<>();
        long ret = 0, sum = 0;
        int kind = 0;

        for(int i = 0; i < nums.size(); i++){
            sum += nums.get(i);
            hash.put(nums.get(i), hash.getOrDefault(nums.get(i), 0) + 1);
            if(hash.get(nums.get(i)) == 1) { kind++;}


            if(i < k - 1) { continue;}

            if(kind >= m) { ret = Math.max(ret, sum);};
            sum -= nums.get(i - k + 1);
            hash.put(nums.get(i - k + 1), hash.get(nums.get(i - k + 1)) - 1);
            if(hash.get(nums.get(i - k + 1)) == 0) { kind--;}
        }
        return ret;
    }

    public static long maximumSubarraySum1(int[] nums, int k) {
        Set<Integer> hash = new HashSet<>();
        int ret = 0, sum = 0;

        for(int i = 0; i < nums.length; i++){
            if(!hash.contains(nums[i])){
                sum += nums[i];
                hash.add(nums[i]);
            }else{
                sum = nums[i];
                hash = new HashSet<Integer>();
            }

            if(hash.size() < k) { continue;}
            if(hash.size() == k) { ret = Math.max(ret, sum);}

            sum -= nums[i - k + 1];
            hash.remove(nums[i - k + 1]);
        }
        return hash.size() == k ? ret : 0;
    }

    public static long maximumSubarraySum(int[] nums, int k) {
        int n = nums.length;
        long ret = 0, sum = 0;
        Map<Integer, Integer> hash = new HashMap<>();
        for(int i = 0; i < k; i++){
            sum += nums[i];
            hash.put(nums[i], hash.getOrDefault(nums[i], 0) + 1);
        }
        if(hash.size() == k){
            ret = Math.max(ret, sum);
        }
        for(int i = k; i < n; i++){
            sum += nums[i];
            hash.put(nums[i], hash.getOrDefault(nums[i], 0) + 1);

            sum -= nums[i - k];
            int count = hash.get(nums[i - k]);
            if(count == 1){
                hash.remove(nums[i - k]);
            }else{
                hash.put(nums[i - k], count - 1);
            }

            if(hash.size() == k){
                ret = Math.max(ret, sum);
            }
        }
        return ret;
    }

    public int maxSatisfied(int[] customers, int[] grumpy, int minutes) {
        int total = 0,n =customers.length;
        for(int i = 0; i < n; i++){
            if(grumpy[i] == 0){
                total += customers[i];
            }
        }
        for(int i = 0; i < minutes; i++){
            if(grumpy[i] == 1) { total += customers[i];}
        }

        int ret = total;
        for(int i = minutes; i < n; i++){
            if(grumpy[i] == 1) { total += customers[i];}
            if(grumpy[i - minutes] == 1) { total -= customers[i - minutes];}
            ret = Math.max(ret, total);
        }
        return ret;
    }

    public int[] decrypt(int[] code, int k) {
        int n = code.length;
        if(k == 0){
            return new int[n];
        }

        int[] ret = new int[n];
        int[] newCode = new int[n * 2];
        System.arraycopy(code, 0, newCode, 0, n);
        System.arraycopy(code, 0, newCode, n, n);
        int left = k > 0 ? 1 : n + k;
        int right = k > 0 ? k : n - 1;
        int count = 0;
        for(int i = left; i <= right; i++){
            count += newCode[i];
        }
        for(int i = 0; i < n; i++){
            ret[i] = count;
            count -= newCode[left];
            count += newCode[right + 1];
            left++;
            right++;
        }
        return ret;
    }

    public int[] decrypt2(int[] code, int k) {
        int n = code.length;
        int[] ret = new int[n];
        int right = k > 0 ? k + 1 : n;
        k = Math.abs(k);

        int sum = 0;
        for(int i = right - k; i < right; i++){
            sum += code[i];
        }
        for(int i = 0; i < n; i++){
            ret[i] = sum;
            sum += code[right % n] - code[(right - k) % n];
            right++;
        }
        return ret;
    }

    public static void main(String[] args) {
//        String b = "WBBWWBBWBW";
//        System.out.println(minimumRecolors(b, 7));

        int[] num = new int[]{1,5,4,2,9,9,9};
        System.out.println(maximumSubarraySum(num, 3));
    }
}
